/*
 * @lc app=leetcode.cn id=70 lang=golang
 *
 * [70] 爬楼梯
 */

// 3. 递归 优化，使用了一个map把已经计算的节点存起来，无需重复计算
// @lc code=start
func climbStairs(n int) int {
	mm := make(map[int]int)

	var recursion func(m int) int
	recursion = func(m int) int {
		if m == 1 || m == 2 {
			return m
		}

		if _, ok := mm[m-1]; !ok {
			mm[m-1] = recursion(m - 1)
		}
		t1 := mm[m-1]

		if _, ok := mm[m-2]; !ok {
			mm[m-2] = recursion(m - 2)
		}
		t2 := mm[m-2]

		return t1 + t2
	}

	return recursion(n)
}

// @lc code=end

// 2. 迭代
// @lc code=start
func climbStairs(n int) int {
	if n == 1 || n == 2 {
		return n
	}

	f1, f2, f3 := 1, 2, 3
	for i := 3; i <= n; i++ {
		f3 = f1 + f2
		f1 = f2
		f2 = f3
	}

	return f3
}

// @lc code=end

// 1. 递归 超时
// @lc code=start
func climbStairs(n int) int {
	if n == 1 || n == 2 {
		return n
	}

	return climbStairs(n-1) + climbStairs(n-2)
}

// @lc code=end

